/*
 *  Merge more than two sored array
 */
package algs4;

import java.util.Random;

import algs4.ds.IndexMinPQ;
import algs4.sort.Insertion;

public class Multiway
{
    public static void main(String[] args) {
        int[]       idx = new int[4];
        Integer[][] a   = new Integer[4][6];
        Random      r   = new Random(System.currentTimeMillis());

        // generate test data
        for (int i = 0; i < 4; i++) {
            idx[i] = 0;

            for (int j = 0; j < 6; j++)
                a[i][j] = r.nextInt(100);

            Insertion.sort(a[i]);
        }

        // create index PQ
        IndexMinPQ<Integer> pq = new IndexMinPQ<>(4);

        // initialize
        for (int i = 0; i < 4; i++)
            pq.insert(i, a[i][idx[i]++]);

        // multiway merge
        while (!pq.isEmpty()) {
            System.out.printf("%2d ", pq.minKey());

            int i = pq.delMin();

            if (idx[i] < 6) pq.insert(i, a[i][idx[i]++]);
        }
        System.out.println();
    }
}
